---
title: "6、交换瓶子"
created: 2025-11-28
tags:
  - 算法
---

# 6、交换瓶子

## 题目 [交换瓶子](https://www.lanqiao.cn/paper/3860/problem/126/)

![[image-7611bd61.png]]

## 思路分析

用的上次贪心的结论 最少交换数就是逆序对的数量

然后就直接归并排序模版套上去了 参考：超快速排序

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=1e4+10;
int a[N];

LL merge_sort(int q[],int l,int r)
{
    if(l>=r)
        return 0;

    int mid= l + r >> 1;
    LL res=merge_sort(q,l,mid) + merge_sort(q,mid+1,r);

    int k=0,i=l,j=mid+1,tmp[r-l+1];
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j])
            tmp[k++]=q[i++];
        else
        {
            tmp[k++]=q[j++];
            res+=mid-i+1;
        }
    }
    while(i<=mid)
        tmp[k++]=q[i++];
    while(j<=r)
        tmp[k++]=q[j++];
    for(i=l,k=0;i<=r;i++,k++)
        q[i]=tmp[k];

    return res;
}

int main()
{
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>a[i];
  cout<<merge_sort(a,0,n-1);
  return 0;
}
```

![[image-4a04220b.png]]

靠 想了半天才发现 这题不是只能相邻交换 它是可以任意交换的 所以逆序对的性质在这里不适用

不能飘啊 看到一个东西觉得眼熟就乱套性质

这题正解是 确定好正确的状态 a[0]=0 a[1]=1……

然后发现某个位置不是正确的数 就说明错位了 把这个数放到它应该放的地方去 直到这个位置上的数也放成了正确的数

![[image-6f319667.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e4+10;

int a[N],ans,n;

int main() {

    cin>>n;

    for(int i=1;i<=n; i++)

        scanf("%d", &a[i]);

    for(int i=1; i<=n; i++) {

        while(a[i]!=i) {

            swap(a[i], a[a[i]]);

            ++ans;

        }

    }

    cout<<ans;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/历年真题 模考特训/第七届 c++ B组 省赛/5、四平方和|5、四平方和]] 🏠 [[00-刷题理模型]] ➡️ [[7、最大比例|7、最大比例]]